package com.itheima.datastructure.demo1;

public class ArrangeCoin {
    public static void main(String[] args) {
        System.out.println(arrangeCoins(10));
        System.out.println(arrangeCoins2(10));
    }

    public static int arrangeCoins(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Input must be non-negative");
        }
        int count = 0;
        int i = 1;
        while (n >= 0) {  // 优化循环终止条件
            n -= i;
            count++;
            i++;
        }
        return count - 1;
    }

    public static int arrangeCoins2(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Input must be non-negative");
        }
        int low = 0, high = n;
        while (low <= high) {
            int mid = (low + high) >>> 1;  // 使用 >>> 避免溢出
            long cost = (long) mid * (mid + 1) / 2;  // 计算需要的硬币数
            if (cost == n) {
                return mid;
            } else if (cost > n) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low - 1;
    }

}